import java.util.*;

//最小覆盖子串
public class MinWindow {
}
class MinWindowSolution {
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        int sn = ss.length;
        int tn = ts.length;
        if(tn>sn)return "";
        HashMap<Character,Integer> lessMap = new HashMap();
        HashMap<Character,Integer> moreMap = new HashMap();
        HashSet<Character> chaset = new HashSet();
        for(Character cha:ts){
            chaset.add(cha);
            mapAdd(lessMap,cha);
        }
        int l = 0;
        int r = -1;
        int start = 0;
        int end = -1;
        int len = sn;
        while(true){
            if(lessMap.size()==0){
                if(len>=r-l+1){
                    start = l;
                    end = r;
                    len = r-l+1;
                }
                if(chaset.contains(ss[l])&&moreMap.containsKey(ss[l]))
                    mapDel(moreMap,ss[l]);
                else if(chaset.contains(ss[l]))
                    mapAdd(lessMap,ss[l]);
                l++;
            }else{
                if(++r<sn){
                    if(chaset.contains(ss[r])&&lessMap.containsKey(ss[r]))
                        mapDel(lessMap,ss[r]);
                    else if(chaset.contains(ss[r]))
                        mapAdd(moreMap,ss[r]);
                }else break;
            }
        }
        return end==-1?"":s.substring(start,end+1);
    }
    void mapAdd(HashMap<Character,Integer> map,char cha){
        if(map.containsKey(cha))
            map.put(cha,map.get(cha)+1);
        else
            map.put(cha,1);
    }
    void mapDel(HashMap<Character,Integer> map,char cha){
        if(map.get(cha)>1){
            map.put(cha,map.get(cha)-1);
        }
        else{
            map.remove(cha);
        }
    }
}